package Lee_code;

import java.util.List;

public class Lee_139_2 {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        int words_len = wordDict.size();
        int[] dp = new int[len+1];

        //先物品后背包
        for (int i=0; i<words_len; i++){
            String temp = wordDict.get(i);
            int temp_len = temp.length();
            for (int j=temp_len; j<=len; j++){
                if(s.substring(j-temp_len, j+1).equals(temp)) {
                    dp[j] = Math.max(dp[j], dp[j - temp_len] + temp_len);
                }
            }
        }

        return dp[len]==len;
    }
}
